package leetCode;

import java.util.Stack;

/**
 * 5. 最长回文子串
 *
 给你一个字符串 s，找到 s 中最长的回文子串。

 示例 1：
 输入：s = "babad"
 输出："bab"
 解释："aba" 同样是符合题意的答案。

 示例 2：
 输入：s = "cbbd"
 输出："bb"

 提示：
 1 <= s.length <= 1000
 s 仅由数字和英文字母组成
 */
public class LongestPalindrome {
    public static void main(String[] args) {
        System.out.println(longestPalindrome2("cbbd"));
    }

    // 暴力，超出时间限制
    public static String longestPalindrome(String s) {
        StringBuilder res = new StringBuilder();
        int max = 0;
        if (s.length() == 1) {
            return s;
        }
        for (int i = 0;i < s.length() - 1;i++) {
            for (int j = i + 1;j < s.length();j++) {
                StringBuilder sb = new StringBuilder(s.substring(i,j+1));
                if (sb.length() > max && new StringBuilder(sb).reverse().toString().equals(sb.toString())) {
                    max = Math.max(max, sb.length());
                    res = sb;
                }
            }
        }
        return res.length() == 0 ? String.valueOf(s.charAt(0)) : res.toString();
    }

    // 中心扩散
    public static String longestPalindrome2(String s) {
        if (s.length() == 0) {
            return "";
        }
        int left = 0;
        int right = 0;
        String cur = "";
        String max = "";
        for (int i = 0;i < s.length();i++) {
            left = i - 1;
            right = i + 1;
            int len = 0;
            while (left >= 0 && s.charAt(left) == s.charAt(i)) {
                left--;
                len++;
            }
            while (right < s.length() && s.charAt(right) == s.charAt(i)) {
                right++;
                len++;
            }
            while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
                left--;
                right++;
                len += 2;
            }
            left = left > 0 ? left : 0;
            cur = s.substring(left, left + len + 1);
            max = (cur.length() > max.length() ? cur : max);
        }
        return max;
    }
}
